package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TreeProblem;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * https://leetcode.com/problems/n-ary-tree-postorder-traversal/
 *
 * @author tzp
 * @since 2020/9/7
 */
public class LC590 implements TreeProblem {
    public static void main(String[] args) {


        Node node2 = new Node(2);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node3 = new Node(3, Arrays.asList(node5, node6));
        Node node1 = new Node(1, Arrays.asList(node3, node2, node4));
        List<Integer> postorder = new LC590.Solution().postorder(node1);
        System.out.println(postorder);
    }

    // Definition for a Node.
    static class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }


    static class Solution {
        public List<Integer> postorder(Node root) {
            Stack<Node> nodes = new Stack<>();
            nodes.push(root);
            ArrayList<Integer> result = new ArrayList<>();
            if (root != null) {
                pushChild(nodes, root);
                while (nodes.size() > 0) {
                    Node x = nodes.pop();
                    result.add(x.val);
                }
            }
            return result;
        }

        public void pushChild(Stack<Node> nodes, Node node) {
            Node c = node;
            if (c != null) {
                if (c.children != null) {
                    for (int i = c.children.size() - 1; i >= 0; i--) {
                        nodes.push(c.children.get(i));
                        pushChild(nodes, c.children.get(i));
                    }
                }
            }
        }
    }
}
